/*
	Name : Rushikesh M Fanse
	Roll No : 16
	Div : H
	Assignment : page replacement algorithm 
*/
#include<cstdio>
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;

int len,frames,page_fault=0,page_hit=0,method,var;
int a[30][30],b[30][30];

int approach(int index)
{
	switch(method)
	{
		case 0:
		{
			int cnt,max=0,max_j,ind,x;
			//FCFS
			for(int j=1;j<=frames;j++)
			{	
				cnt=0;
				
				ind=index;
				x=a[j][ind-1];
				while(1)
				{
					if(a[j][ind-2]==x&&(ind-2)!=-1)
					{
						cnt++;
					}
					else
					{
						break;
					}
					ind--;
					
				}
				if(max<cnt)
				{
					max=cnt;
					max_j=j;
				}
			}
			return max_j;
		}
		break;
		case 1:
		{
			//LRU
			int cnt=frames,ind,flag=0,x,flag1=1,j;
			ind=index;
			while(1)
			{
				while(ind&&flag1==1)//finds the element which is in the index column
				{
					ind--;
					for(j=1;j<=frames;j++)
					{
						if(a[j][index-1]==a[0][ind])
						{
							flag=1;
							break;
						}
						if(flag==1)
						{
							flag1=0;
							break;
						}
					}
					if(flag==1)
					{
				//		flag1=0;
						flag=0;
						break;
					}
				}
				if(cnt==frames)
				{
					x=a[0][ind];
				//	ind--;
					cnt--;
					flag1=1;
					continue;
				}
				else
				{
					if(a[0][ind]==a[0][ind+1])//same element continue
					{
						ind--;
						continue;
					}
					else//the element of the column is found
					{
						cnt--;
						flag1==1;
						if(cnt==0)
							return j;
					}
				}
			}
		}
		break;
		case 2:
		{
			//optimal
			int o[frames][2],i=0,flag=0,cnt=0,max=0,max_j;
			for(int l=1;l<=frames;l++)
			{
				o[l][1]=99;
			}
			for(int l=1;l<=frames;l++)
			{
				o[l][0]=a[l][index-1];
			}
			int ind=index;
			while(ind<len)
			{
				i++;
				ind++;
				for(int l=1;l<=frames;l++)
				{
					if(o[l][0]==a[0][ind])
					{
						cnt++;
						o[l][1]=i;
						flag=1;
					}
				}	
				if(cnt==frames)
					break;
				if(flag==0)
					continue;
				if(flag==1)
					flag=0;
			}
			if(i==1)
			{
				return 20;
			}
			for(int l=1;l<=frames;l++)
			{
				if(max<o[l][1])
				{
					max=o[l][1];
					max_j=l;
				}
			}
			return max_j;
		}
		break;
	}
}
void print_A()
{	
	for(int i=0;i<=frames;i++)
	{
		for(int j=0;j<len;j++)
			cout<<a[i][j]<<"\t";
		cout<<"\n";
	}
}
int main()
{
	int index_to_replace;
	cout<<"enter no of pages in refernce string";
	cin>>len;
	
	cout<<"enter the no of frames";
	cin >>frames;
	for(int i=1;i<=frames;i++)
		for(int j=0;j<len;j++)
			a[i][j]=-1;
	
	cout<<"enter the pages in reference string";
	for(int i=0;i<len;i++)
	{
		cin>>a[0][i];
	}
	
	for(int i=0;i<=frames;i++)
		for(int j=0;j<len;j++)
			b[i][j]=a[i][j];

	while(method<=2)
	{	
		page_fault=0;
		page_hit=0;
		switch(method)
		{
			case 0:
				cout<<"FCFS\n";
			break;
			case 1:
				cout<<"LRU\n";
			break;
			case 2:
				cout<<"OPTIMAL\n";
			break;
		/*	case 3:
				cout<<"\n";
			break;*/
		}
		int k=0;
		for(int i=0;i<len;i++)
		{
			int flag=0;
			for(int j=1;j<=frames;j++)
			{
				if(a[j][i-1]==-1||i==0)
				{
					page_fault++;
					a[j][i]=a[0][i];
					flag=1;
					for(int l=1;l<=frames;l++)
						a[l][i+1]=a[l][i];
					break;
				}
			}
			if(flag==0)
			{	
				for(int j=1;j<=frames;j++)
				{
					if(a[j][i-1]==a[0][i])
					{
						flag=1;
						break;
					}
					
				}
				if(flag==1)
				{
					
					page_hit++;
					for(int j=1;j<=frames;j++)
					{
						a[j][i]=a[j][i-1];
					}
				}
				else
				{	var=i;
					page_fault++;
					index_to_replace=approach(i);
					for(int j=1;j<=frames;j++)
					{
						if(j==index_to_replace)
						{
							a[index_to_replace][i]=a[0][i];
						}
						else
						{
							a[j][i]=a[j][i-1];
						}
					}	
				}
				
			}
		
		}
		
		for(int i=0;i<=frames;i++)
		{
			
			for(int j=0;j<len;j++)
				{	
					cout<<a[i][j]<<"\t";
					a[i][j]=b[i][j];
				}
			cout<<"\n";
		}
		cout<<"page hit : "<<page_hit<<" page fault : "<<page_fault<<"\n";
		method++;
		
	}
	return 0;
}

/*
	OUTPUT:
	rishi@rishi-PC:~$ ./a.out
	enter no of pages in refernce string11
	enter the no of frames3
	enter the pages in reference string1 2 3 1 2 4 1 4 2 3 2
	FCFS
	1	2	3	1	2	4	1	4	2	3	2	
	1	1	1	1	1	4	4	4	4	3	3	
	-1	2	2	2	2	2	1	1	1	1	1	
	-1	-1	3	3	3	3	3	3	2	2	2	
	page hit : 4 page fault : 7
	LRU
	1	2	3	1	2	4	1	4	2	3	2	
	1	1	1	1	1	1	1	1	1	3	3	
	-1	2	2	2	2	2	2	2	2	2	2	
	-1	-1	3	3	3	4	4	4	4	4	4	
	page hit : 6 page fault : 5
	OPTIMAL
	1	2	3	1	2	4	1	4	2	3	2	
	1	1	1	1	1	1	1	1	1	3	3	
	-1	2	2	2	2	2	2	2	2	2	2	
	-1	-1	3	3	3	4	4	4	4	4	4	
	page hit : 6 page fault : 5

*/
